home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / inet / internet-drafts / draft-ietf-tcplw-extensions-00.txt < prev    next >
Encoding:
Text File  |  1993-07-08  |  18.9 KB  |  586 lines
  1.  
  2. Internet Draft                                                 R. Braden
  3. Expires: December 1993                                               ISI
  4.                                                            June 21, 1993
  5.  
  6.  
  7.              TCP Extensions for High Performance: An Update
  8.  
  9. Status of This Memo
  10.  
  11.    This document is an Internet-Draft.  Internet-Drafts are working
  12.    documents of the Internet Engineering Task Force (IETF), its Areas,
  13.    and its Working Groups.  Note that other groups may also distribute
  14.    working documents as Internet-Drafts.
  15.  
  16.    Internet-Drafts are draft documents valid for a maximum of six
  17.    months.  Internet-Drafts may be updated, replaced, or obsoleted by
  18.    other documents at any time.  It is not appropriate to use Internet-
  19.    Drafts as reference material or to cite them other than as a
  20.    ``working draft'' or ``work in progress.''
  21.  
  22. Abstract
  23.  
  24.    This memo is a contribution to the TCP Large Windows (TCPLW) Working
  25.    Group.  It presents some suggested modifications to RFC-1323, which
  26.    defined TCP extensions to improve performance over large
  27.    bandwidth*delay product paths and to provide reliable operation over
  28.    very high-speed paths.
  29.  
  30. 1. INTRODUCTION
  31.  
  32.    RFC-1323 [Jacobson92] defined a set of extensions to the TCP protocol
  33.    [Postel81] to improve performance over large bandwidth*delay product
  34.    paths and to provide reliable operation over very high-speed paths.
  35.  
  36.    Specifically, RFC-1323 defined three new mechanisms.
  37.  
  38.    (1)  Window Scale Option
  39.  
  40.         A new TCP option, "Window Scale" allows windows larger than
  41.         2**16 bytes.  This option defines an implicit scale factor,
  42.         which is used to multiply the window size value found in a TCP
  43.         header to obtain the true window size.
  44.  
  45.    (2)  RTTM: Round-Trip Time Measurement
  46.  
  47.         A new TCP option "Timestamps" is introduced, and a mechanism
  48.         called "RTTM"  (Round Trip Time Measurement) uses this option to
  49.         obtain improved measurement of round trip times (RTTs).
  50.  
  51.  
  52.  
  53. Braden                   Expires: December 1993                 [Page 1]
  54.  
  55.  
  56.  
  57.  
  58. Internet Draft     TCP Performance Extensions: Update          June 1993
  59.  
  60.  
  61.    (3)  PAWS: Protect Against Wrapped Sequence
  62.  
  63.         The Timestamps option is used by the PAWS mechanism to extend
  64.         TCP reliability to transfer rates well beyond the foreseeable
  65.         upper limit of network bandwidths, with reasonably large values
  66.         of the Maximum Segment Lifetime (MSL).
  67.  
  68.    The present document summarizes several minor issues and
  69.    clarifications that have accumulated since RFC-1323 was published.
  70.  
  71. 2. MODIFICATIONS TO RFC-1323
  72.  
  73.    2.1  RTTM: Clarify Relationship to Karn's Algorithm
  74.  
  75.       TCP requires that the RTO (retransmission timeout) values used for
  76.       successive retransmissions of the same segment form an increasing
  77.       sequence [Postel81]; this is known as "retransmission back-off".
  78.       TCP implementations have previously been required [RFC-1323] to
  79.       use Phil Karn's algorithm [Karn87], which states that (1)
  80.       retransmission back-off will persist until the next ACK is
  81.       received for a data segment that has never been retransmitted, and
  82.       that (2) no RTT measurements will be made from acknowledgments of
  83.       retransmitted data segments.  Karn's algorithm was designed to
  84.       allow reliable RTT estimates despite an ambiguity when an ACK is
  85.       received for a retransmitted data segment: the ACK may have been
  86.       created from either the original or the retransmission [Zhang86].
  87.  
  88.       However, as RFC-1323 implied but did not clearly state, the RTTM
  89.       mechanism replaces Karn's algorithm.  With the RTTM mechanism in
  90.       operation, an ACK segment will echo the timestamp from whichever
  91.       data segment triggered the ACK.  This removes the ambiguity in RTT
  92.       measurement that required the Karn algorithm.  For compatibility,
  93.       however, an implementation of RFC-1323 must still be prepared to
  94.       use the Karn algorithm when talking with a host that does not
  95.       implement RFC-132.
  96.  
  97.       Overriding the Karn algorithm was implied by the following
  98.       statement on page 14 of RFC-1323, which was independent of whether
  99.       or not the new data being acknowledged has been retransmitted:
  100.  
  101.            "A TSecr value received in a segment is used to update the
  102.            averaged RTT measurement only if the segment acknowledges
  103.            some new data, i.e., only if it advances the left edge of the
  104.            send window."
  105.  
  106.  
  107.  
  108.  
  109.  
  110.  
  111.  
  112. Braden                   Expires: December 1993                 [Page 2]
  113.  
  114.  
  115.  
  116.  
  117. Internet Draft     TCP Performance Extensions: Update          June 1993
  118.  
  119.  
  120.    2.2  RTTM: Discuss When RTT Measurements are Made
  121.  
  122.       The RFC-1323 text quoted immediately above implies that duplicate
  123.       acknowledgments will not contribute to measurement of the RTT,
  124.       even with RTTM in use.
  125.  
  126.       Suppose that exactly one segment is lost from a window of N
  127.       segments.  If there are no delayed ACKs or lost segments, this
  128.       will result in a string of N-1 duplicate ACKs arriving at the
  129.       sender.  RTTM can make no new RTT measurement for at least N
  130.       packet times, so the first new measurement will come from the ACK
  131.       triggered by retransmission of the lost packet.  Therefore, the
  132.       discussion under bullet (B) on page 15 of RFC-1323 is gratuitous:
  133.       no matter which timestamp is echoed in a duplicate ACK segment, it
  134.       (the echoed timestamp) will be ignored.
  135.  
  136.       This issue deserves further discussion.  We see that with one
  137.       dropped segment per window, RTTM may result in only one RTT
  138.       measurement per window.  However, this is still a significant
  139.       improvement over a standard TCP without RTTM, which will make even
  140.       fewer measurements; it cannot measure the retransmitted packet,
  141.       due to Karn's algorithm.
  142.  
  143.       However, we should ask whether it would be possible to do any
  144.       better than one measurement per RTT.  The reason for making a new
  145.       RTT measurement only when new data is acknowledged is to avoid
  146.       artificial inflation of the RTT value, as illustrated by the
  147.       diagram on the top of page 14 of RFC-1323.  We would need an
  148.       alternative criterion for making a measurement that would also
  149.       prevent such inflation of the RTT measurements.
  150.  
  151.       For example, suppose that the transmitter made a new RTT
  152.       measurement only when it had outstanding data, i.e., only when
  153.       SND_NXT > SND_UNA.  The following example, involving simultaneous
  154.       data transmission from both sides, shows that this alternative
  155.       criterion may still allow RTT inflation.  Here the TSrecent values
  156.       on each side are shown in parentheses, and TCP A sends data blocks
  157.       a, b, ... and TCP B sends data blocks x, y, ...
  158.  
  159.  
  160.  
  161.  
  162.  
  163.  
  164.  
  165.  
  166.  
  167.  
  168.  
  169.  
  170.  
  171. Braden                   Expires: December 1993                 [Page 3]
  172.  
  173.  
  174.  
  175.  
  176. Internet Draft     TCP Performance Extensions: Update          June 1993
  177.  
  178.  
  179.  
  180.          TCP  A                                          TCP B
  181.  
  182.        (TSrecent)                                      (TSrecent)
  183.  
  184.       1.         <a,TSval=1,TSecr=1...>         ------>       (1)
  185.  
  186.       2.  (127)  <-----      <X,ACK(a),TSval=127,TSecr=1>    (1)
  187.  
  188.       3.  (127)  <ACK(x),TSval=5,TSecr=127>    ------>       (5)
  189.  
  190.              . . . ( Pause for 60 timestamp clock ticks ) . . . .
  191.  
  192.       4.  (127)  <b,ACK(x),TSval=65,TSecr=127> --->  ...
  193.  
  194.       5.            ... <--- <y,ACK(a),TSval=191,TSecr=5>    (5)
  195.  
  196.       4'.               <b,ACK(x),TSval=65,TSecr=127> --->  (65)
  197.  
  198.       5'.  (191)  <-- <y,ACK(a),TSval=191,TSecr=5>
  199.  
  200.       6.            ... <--- <y,ACK(b),TSval=195,TSecr=65>  (65)
  201.  
  202.       7.  (191)  <b,ACK(y),TSval=68,TSecr=191> --->  ...
  203.  
  204.  
  205.       In this symmetrical data transfer example, both sides send data
  206.       simultaneously (lines 4 and 5) after a pause of roughly 60 time
  207.       units.  When these segments arrive (lines 4' and 5'), each side
  208.       has outstanding data and by the proposed rule would use the TSecr
  209.       to update its RTT estimate.  However, this would result in
  210.       inflating ech of these RTT estimates by the 60 time units.
  211.  
  212.       We believe that the only way to ensure that the measured RTT is
  213.       accurate is to accept TSecr only when new data is acknowledged.
  214.       Thus, the RFC-1323 tule quoted at the end of the preceding section
  215.       is the best that can be done, and duplicate ACKs cannot update the
  216.       RTT estimate.
  217.  
  218.    2.3  RTTM: Which Timestamp to Echo?
  219.  
  220.       RFC-1323 presented the following algorithm to control which
  221.       timestamp is echoed:
  222.  
  223.       (1)  "The connection state is augmented with two 32-bit slots:
  224.            TS.Recent holds a timestamp to be echoed in TSecr whenever a
  225.            segment is sent, and Last.ACK.sent holds the ACK field from
  226.            the last segment sent.  Last.ACK.sent will equal RCV.NXT
  227.  
  228.  
  229.  
  230. Braden                   Expires: December 1993                 [Page 4]
  231.  
  232.  
  233.  
  234.  
  235. Internet Draft     TCP Performance Extensions: Update          June 1993
  236.  
  237.  
  238.            except when ACKs have been delayed.
  239.  
  240.       (2)  If Last.ACK.sent falls within the range of sequence numbers
  241.            of an incoming segment:
  242.  
  243.               SEG.SEQ <= Last.ACK.sent < SEG.SEQ + SEG.LEN
  244.  
  245.            then the TSval from the segment is copied to TS.Recent;
  246.            otherwise, the TSval is ignored.
  247.  
  248.       (3)  When a TSopt is sent, its TSecr field is set to the current
  249.            TS.Recent value."
  250.  
  251.       Step (2) of this algorithm is incorrect in two regards: (1) it
  252.       will fail to update TSrecent for a retransmitted segment that
  253.       resulted from a lost ACK, and (2) it will fail if SEG.LEN = 0
  254.       [Borman93,Skibo93].
  255.  
  256.       The correct step (2) is actually simpler.  It is as follows:
  257.  
  258.            (2)  If: SEG.TSval >= TSrecent and SEG.SEQ <= Last.ACK.sent
  259.                 then SEG.TSval is copied to TS.Recent; otherwise, it is
  260.                 ignored.
  261.  
  262.       Observe that this algorithm explicitly constructs a monotonic
  263.       sequence of TSrecent values.  The case SEG.TSval = TSrecent is
  264.       included here for consistency with the PAWS test.
  265.  
  266.       Note also that RFC-1323 presented this algorithm *correctly* in
  267.       Section 4.2.1 discussing PAWS, but *incorrectly* in the Event
  268.       Processing rules on page 35.
  269.  
  270.    2.4  Implementation of TCP Options
  271.  
  272.       The major implementation chore in the RFC-1323 extensions is
  273.       probably the modifications to allow TCP options in data segments.
  274.       This code must obey the limits set by the MSS (maximum segment
  275.       size) and by the connected network MTU (maximum transmission
  276.       unit).  This issue has sometimes been misunderstood, perhaps
  277.       partly due to a past imprecision in terminology (e.g., what is a
  278.       "segment"?).  In addition, prior attempts to clarify these issues
  279.       have been unfortunately obscure [RFC-1122].
  280.  
  281.       To send a segment, the general procedure for a TCP should be:
  282.  
  283.       (a)  Get a packet buffer and create a TCP header in it.
  284.  
  285.       (b)  Format any required TCP options into the buffer.
  286.  
  287.  
  288.  
  289. Braden                   Expires: December 1993                 [Page 5]
  290.  
  291.  
  292.  
  293.  
  294. Internet Draft     TCP Performance Extensions: Update          June 1993
  295.  
  296.  
  297.       (c)  Copy 'len' bytes of data into the buffer, where:
  298.  
  299.                 len = min( data_to_send, maxseg, maxoptdata - optlen );
  300.  
  301.       Here:
  302.  
  303.       *    data_to_send = Amount of data to be sent.
  304.  
  305.       *    maxseg = "Normal" data length in a segment.
  306.  
  307.       *    maxoptdata =  Largest <data + TCP options> area permitted.
  308.  
  309.       *    optlen = length of TCP options added in (b).
  310.  
  311.       Finally, we must define how to compute 'maxseg' and 'maxoptdata'.
  312.  
  313.           maxoptdata = min( Received_MSS, pathMTU - 40) -
  314.  
  315.                                       <max IP option length>
  316.  
  317.           maxseg = maxoptdata - <size of 'normal' TCP options>
  318.  
  319.       Here "Received_MSS" is the value received in an MSS option in a
  320.       SYN segment, or 536 if none is received.  The MTU over the path,
  321.       "pathMTU", may be found by MTU Discovery, or it may be determined
  322.       by the following heuristic:  use "interface_MTU" if the
  323.       destination is on the connected network, else use 576.  In normal
  324.       usage today, there are no IP options to be considered.
  325.  
  326.       An MSS option is intended to specify ONLY a property of the remote
  327.       host, independent of the path: the largest IP datagram that can be
  328.       received and reassembled (less 40).  For those hosts that have no
  329.       limit on datagram size, it would not be incorrect to specify
  330.       "infinity" (65535) in its MSS option.  However, a more sensible
  331.       choice would be "interface_MTU".
  332.  
  333.       Note also that 'maxseg' is also used by the SWS (silly-window
  334.       syndrome) and congestion control algorithms of TCP [RFC-1122], and
  335.       it may correspond to the "normal" data block size for a segment
  336.       used in bulk transmission.
  337.  
  338. 3. SUMMARY OF ALGORITHMS
  339.  
  340.    Appendix E of RFC-1323 defined the overall algorithm as modifications
  341.    of the TCP Event Processing rules.  This section contains a more
  342.    concise and algorithmic description.
  343.  
  344.    We define the following symbols:
  345.  
  346.  
  347.  
  348. Braden                   Expires: December 1993                 [Page 6]
  349.  
  350.  
  351.  
  352.  
  353. Internet Draft     TCP Performance Extensions: Update          June 1993
  354.  
  355.  
  356.    Options
  357.  
  358.        WSopt:       TCP Window Scale Option
  359.        TSopt:       TCP Timestamps Option
  360.  
  361.    Option Fields
  362.  
  363.        shift.cnt:   Window scale byte in WSopt.
  364.        TSval:       32-bit Timestamp Value field in TSopt.
  365.        TSecr:       32-bit Timestamp Reply field in TSopt.
  366.  
  367.    Option Fields in Current Segment
  368.  
  369.        SEG.TSval:   TSval field from TSopt in current segment.
  370.        SEG.TSecr:   TSecr field from TSopt in current segment.
  371.        SEG.WSopt:   8-bit value in WSopt
  372.  
  373.    Clock Values
  374.  
  375.        my.TSclock:      Local source of 32-bit timestamp values
  376.        my.TSclock.rate: Period of my.TSclock (1 ms to 1 sec per tick).
  377.  
  378.    Per-Connection State Variables
  379.  
  380.        TS.Recent:       Latest received Timestamp
  381.        Last.ACK.sent:   Last ACK field sent
  382.  
  383.        Snd.TS.OK:       1-bit flag
  384.        Snd.WS.OK:       1-bit flag
  385.  
  386.        Rcv.Wind.Scale:  Receive window scale power
  387.        Snd.Wind.Scale:  Send window scale power
  388.  
  389.        Start.Time:      my.TSclock value when segment being timed was
  390.                         sent (used by pre-1323 code).
  391.  
  392.    Procedure
  393.  
  394.        Update_SRTT( m ) Procedure to update the smoothed RTT and RTT variance
  395.                         estimates, using the rules of [Jacobson88], given m,
  396.                         a new RTT measurement.
  397.  
  398.  
  399.    PSEUDO-CODE SUMMARY:
  400.  
  401.    Create new TCB => {
  402.          Rcv.wind.scale =
  403.              MIN( 14, MAX( 0, floor(log2(receive buffer space)) - 15 ) );
  404.  
  405.  
  406.  
  407. Braden                   Expires: December 1993                 [Page 7]
  408.  
  409.  
  410.  
  411.  
  412. Internet Draft     TCP Performance Extensions: Update          June 1993
  413.  
  414.  
  415.          Snd.wind.scale = 0;
  416.          Last.ACK.sent = 0;
  417.          Snd.TS.OK = Snd.WS.OK = FALSE;
  418.    }
  419.  
  420.  
  421.    Send initial {SYN} segment => {
  422.  
  423.           SEG.WND = MIN( RCV.WND, 65535 );
  424.           Include in segment: TSopt(TSval=my.TSclock, TCecr=0);
  425.           Include in segment: WSopt = Rcv.wind.scale;
  426.    }
  427.  
  428.  
  429.    Send {SYN, ACK} segment => {
  430.  
  431.           SEG.ACK = Last.ACK.sent = RCV.NXT;
  432.           SEG.WND = MIN( RCV.WND, 65535 );
  433.           if (Snd.TS.OK) then
  434.                  Include in segment: TSopt(TSval=my.TSclock, TSecr=TS.Recent);
  435.           if (Snd.WS.OK) then
  436.                  Include in segment: WSopt = Rcv.wind.scale;
  437.    }
  438.  
  439.  
  440.    Receive {SYN} or {SYN,ACK} segment => {
  441.  
  442.           if (Segment contains TSopt) then {
  443.                  TS.Recent = SEG.TSval;
  444.                  Snd.TS.OK = TRUE;
  445.                  if (is {SYN,ACK} segment) then
  446.                        Update_SRTT(
  447.                             (my.TSclock - SEG.TSecr)*my.TSclock.rate ) ;
  448.           }
  449.  
  450.           if Segment contains WSopt) then {
  451.                  Snd.wind.scale = SEG.WSopt;
  452.                  Snd.WS.OK = TRUE;
  453.           }
  454.           else
  455.                  Rcv.wind.scale = Snd.wind.scale = 0;
  456.    }
  457.  
  458.  
  459.  
  460.    Send non-SYN segment => {
  461.  
  462.           SEG.ACK = Last.ACK.sent = RCV.NXT;
  463.  
  464.  
  465.  
  466. Braden                   Expires: December 1993                 [Page 8]
  467.  
  468.  
  469.  
  470.  
  471. Internet Draft     TCP Performance Extensions: Update          June 1993
  472.  
  473.  
  474.           SEG.WND = MIN( RCV.WND >> Rcv.wind.scale, 65535 );
  475.           if (Snd.TS.OK) then
  476.                  Include in segment: TSopt(TSval=my.TSclock, TSecr=TS.Recent);
  477.    }
  478.  
  479.  
  480.    Receive non-SYN segment in (state >= ESTABLISHED) => {
  481.  
  482.           Window = (SEG.WND << Snd.wind.scale);
  483.                 /* Use 32-bit 'Window' instead of 16-bit 'SEG.WND'
  484.                  * in rest of processing.
  485.                  */
  486.  
  487.           if (Segment contains TSopt) then {
  488.                  if (SEG.TSval < TS.Recent && Idle less than 25 days) then {
  489.                         if (Send.TS.OK
  490.                             AND (NOT RST) ) then {
  491.                                  /* Timestamp too old =>
  492.                                   *    segment is unacceptable.
  493.                                   */
  494.                               Send ACK segment;
  495.                               Discard segment and return;
  496.                         }
  497.                  }
  498.                  else {
  499.                         if (SEG.SEQ =< Last.ACK.sent) then
  500.                                TS.Recent = SEG.TSval;
  501.                  }
  502.           }
  503.  
  504.           if (SEG.ACK > SND.UNA) then {
  505.                        /* (At least part of) first segment in
  506.                         * retransmission queue has been ACKd
  507.                         */
  508.                  if (Segment contains TSopt) then
  509.                         Update_SRTT(
  510.                            (my.TSclock - SEG.TSecr)/my.TSclock.rate);
  511.                  else
  512.                         Update_SRTT( /* for compatibility */
  513.                            (my.TSclock - Start.Time)/my.TSclock.rate);
  514.           }
  515.    }
  516.  
  517.  
  518.  
  519.  
  520.  
  521.  
  522.  
  523.  
  524.  
  525. Braden                   Expires: December 1993                 [Page 9]
  526.  
  527.  
  528.  
  529.  
  530. Internet Draft     TCP Performance Extensions: Update          June 1993
  531.  
  532.  
  533. 4.  REFERENCES
  534.  
  535.  
  536.      [Borman93]  Borman, D., Private communication, 1993.
  537.  
  538.       [Jacobson88]  Jacobson, V., "Congestion Avoidance and Control",
  539.       SIGCOMM '88, Stanford, CA., August 1988.
  540.  
  541.       [Jacobson92]  Jacobson, V., Braden, R., and D. Borman, "TCP
  542.       Extensions for High Performance", RFC-1323, May 1992.
  543.  
  544.       [Karn87]  Karn, P. and C. Partridge, "Estimating Round-Trip Times
  545.       in Reliable Transport Protocols", Proc. SIGCOMM '87, Stowe, VT,
  546.       August 1987.
  547.  
  548.       [Postel81]  Postel, J., "Transmission Control Protocol - DARPA
  549.       Internet Program Protocol Specification", RFC 793, DARPA,
  550.       September 1981.
  551.  
  552.       [RFC-1122]  Braden, R., Ed., "Requirements for Internet Hosts --
  553.       Communication Layers", RFC-1122, October 1989.
  554.  
  555.       [Skibo93]  Skibo, T., Private communication, 1993.
  556.  
  557.       [Zhang86]  Zhang, L., "Why TCP Timers Don't Work Well", Proc.
  558.       SIGCOMM '86, Stowe, Vt., August 1986.
  559.  
  560.  
  561. Security Considerations
  562.  
  563.    Security issues are not discussed in this memo.
  564.  
  565. Authors' Addresses
  566.  
  567.  
  568.    Bob Braden
  569.    University of Southern California
  570.    Information Sciences Institute
  571.    4676 Admiralty Way
  572.    Marina del Rey, CA 90292
  573.  
  574.    Phone: (213) 822-1511
  575.    EMail: Braden@ISI.EDU
  576.  
  577.  
  578.  
  579.  
  580.  
  581.  
  582.  
  583.  
  584. Braden                   Expires: December 1993                [Page 10]
  585.  
  586.